package hot100;

public class Solution395 {
    public int longestSubstring(String s, int k) {
        return dfs(s, 0, s.length() - 1, k);
    }
    private int dfs(String s, int l, int r, int k) {
        if (l > r) {
            return 0;
        }
        int[] cnt = new int[26];
        for (int i = l ; i <= r; i++) {
            cnt[s.charAt(i) - 'a']++;
        }
        char spilt = ' ';
        for (int i = 0; i < 26; i++) {
            if(cnt[i] > 0 && cnt[i] < k) {
                spilt = (char) ('a' + i);
                break;
            }
        }
        if (spilt == ' ') {
            return r - l + 1;
        }
        int max = 0;
        int i = l;
        while (i <= r) {
            while (i <= r && s.charAt(i) == spilt) {
                i++;
            }
            if (i > r) {
                break;
            }
            int start = i;
            while (i <= r && s.charAt(i) != spilt) {
                i++;
            }
            int cur = dfs(s, start, i - 1, k);
            max = Math.max(max, cur);
        }
        return max;
    }

    public static void main(String[] args) {
        Solution395 solution395 = new Solution395();
        System.out.println(solution395.longestSubstring("aaabb", 3));

    }
}
